numbers = [14, 33, 27, 10, 35, 19, 42, 44]


def merge_sort(lo, hi):
    if lo >= hi:
        return
    else:
        mid = int((lo + hi) / 2)
        #print(lo, mid, hi, "\n")
        merge_sort(lo, mid)
        merge_sort(mid + 1, hi)
        merge(lo, mid, hi)


def merge(lo, mid, hi):
    loIndex = lo
    hiIndex = mid

    merged = []
    while True:
        if loIndex < mid and hiIndex <= hi:
            if numbers[loIndex] < numbers[hiIndex]:
                # merged = append(merged, numbers[loIndex])
                merged.append(numbers[loIndex])
                loIndex += 1
            else:
                merged.append(numbers[hiIndex])
                hiIndex += 1

        elif loIndex < mid:
            # array1 单独存在元素
            merged.append(numbers[loIndex])
            loIndex += 1
        elif hiIndex <= hi:
            # array2 单独存在元素
            merged.append(numbers[hiIndex])
            hiIndex += 1

        if loIndex >= mid and hiIndex > hi:
            break

    for i in range(0, len(merged), 1):
        numbers[i + lo] = merged[i]


print("排序前：", numbers)
merge_sort(0, len(numbers) - 1)
print("排序后：", numbers)
